import java.util.*;

interface Cache{
    Object get(Object args);
    void put(Object args,Object res);
}


class LRUcache implements Cache{
    private Map<Object,Object> resMark;
    private int cacheSize;

    LRUcache(int cSize){
        resMark=new LinkedHashMap<>();
        cacheSize=cSize;
    }

    @Override
    public Object get(Object args){
        var res = resMark.getOrDefault(args,null);
        if(res!=null){
            resMark.remove(args);
            resMark.put(args,res);
        }
        return res;
    }

    @Override
    public void put(Object args,Object res){
        while(resMark.size()>=cacheSize){
            resMark.remove(resMark.keySet().iterator().next());
        }
        resMark.put(args, res);
    }
}

class SizeCache implements Cache{
    private Map<Object,Object> resMark;
    private int cacheSize;

    SizeCache(int cSize){
        resMark=new HashMap<>();
        cacheSize=cSize;
    }

    @Override
    public Object get(Object args) {
        return resMark.getOrDefault(args,null);
    }

    @Override
    public void put(Object args, Object res) {
        if(resMark.size()>cacheSize){
            resMark.clear();
        }
        resMark.put(args, res);
    }
}

interface Function {
    Object run(List<Object> args,CacheFuncUtil util);
}


class CacheFuncUtil {

    private Cache cache;

    private Function runFunc;

    CacheFuncUtil(Cache usedCache,Function function){
        cache=usedCache;
        runFunc=function;
    }

    Object runCacheFunc(List<Object> args){
        Object res=cache.get(args);
        if(res==null){
            res=runFunc.run(args,this);
            cache.put(args,res);
        }
        return res;
    }
}



class CacheRunImpl implements Function{
    public int[] getMark(String str){
        int[] mark=new int[26];
        for (int i = 0; i < str.length(); i++) {
            mark[str.charAt(i)-'a']++;
        }
        return mark;
    }

    public boolean judgeEleSame(String str1,String str2){
        var mark1=getMark(str1);
        var mark2=getMark(str2);
        for (int i = 0; i < mark1.length; i++) {
            if(mark1[i]!=mark2[i]){
                return false;
            }
        }
        return true;
    }

    @Override
    public Object run(List<Object> args,CacheFuncUtil cacheUtil) {
        String s1=(String)args.get(0);
        String s2=(String)args.get(1);
        if(s1.length()==0) return true;
        if(s1.length()==1) return s1.equals(s2);
        if(judgeEleSame(s1,s2)==false) return false;
        for (int i = 1; i < s1.length(); i++) {
            if((Boolean)cacheUtil.runCacheFunc(Arrays.asList(s1.substring(0,i), s2.substring(0,i)))&&(Boolean) cacheUtil.runCacheFunc(Arrays.asList(s1.substring(i),s2.substring(i)))){
                return true;
            }
            else if((Boolean)cacheUtil.runCacheFunc(Arrays.asList(s1.substring(0,i), s2.substring(s2.length()-i)))&&(Boolean) cacheUtil.runCacheFunc(Arrays.asList(s1.substring(i),s2.substring(0,s2.length()-i)))){
                return true;
            }
        }
        return false;
    }
}

class Solution87 {
    public boolean isScramble(String s1, String s2){
        CacheRunImpl cacheRun=new CacheRunImpl();
        CacheFuncUtil util=null;
        util = new CacheFuncUtil(new LRUcache(1000), cacheRun);
        return (Boolean) util.runCacheFunc(Arrays.asList(s1, s2));
    }
}